package Sort;

import java.util.ArrayList;

/**
 * 排序(7)
 * 基数排序
 */
public class RadixSort extends Template {

    /**
     * 法二
     *
     * @param array 需排序数组
     */
//    public static void sort(int[] array) {
//        if (array == null || array.length < 2) return;
//        // 1.先算出最大数的位数；
//        int max = array[0];
//        for (int i = 1; i < array.length; i++) {
//            max = Math.max(max, array[i]);
//        }
//        int maxDigit = 0;//最大数的位数
//        while (max != 0) {
//            max /= 10;
//            maxDigit++;
//        }
//        //
//        int mod = 10, div = 1;
//        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
//        for (int i = 0; i < 10; i++)
//            bucketList.add(new ArrayList<Integer>());
//        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
//            for (int j = 0; j < array.length; j++) {
//                int num = (array[j] % mod) / div;
//                bucketList.get(num).add(array[j]);
//            }
//            int index = 0;
//            for (int j = 0; j < bucketList.size(); j++) {
//                for (int k = 0; k < bucketList.get(j).size(); k++)
//                    array[index++] = bucketList.get(j).get(k);
//                bucketList.get(j).clear();
//            }
//        }
//
//
//    }


    /**
     * 法一
     *
     * @param array 需排序数组
     */
    public static void sort(int[] array) {
        //1.计算最大数的位数；
        // 找出最大数max -> 除10取整,非0则位数加1
        int maxDigit = 0;//最大数的位数
        int max = array[0];
        for (int num : array) {
            max = Math.max(max, num);
        }
        System.out.println("最大数" + max);
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        System.out.println("因此最大位数" + maxDigit);

        //2.排序
        int multiple = 1; //每次遍历需要除的10的倍数 1，10，100，1000...
        int digit = 1; //排序所依据的位数 (个位,十位,百位,千位,万位....)。
        int[][] temp = new int[10][array.length]; //数组的第一维表示可能的余数0-9
        int[] order = new int[10]; //数组order[i]用来表示该位是i的数的个数
        while (digit <= maxDigit) {
            int index = 0; //数组下标，重新排列数组元素
            for (int i = 0; i < array.length; i++) {
                int lsd = ((array[i] / multiple) % 10);//lsd：当前位的值
                temp[lsd][order[lsd]] = array[i];
                order[lsd]++;//该位是lsd的数的个数+1
            }
            for (int i = 0; i < 10; i++) {
                if (order[i] != 0)
                    for (int j = 0; j < order[i]; j++) {
                        array[index] = temp[i][j];
                        index++;
                    }
                order[i] = 0;
            }
            multiple *= 10;//倍数*10 下次按照到下一位排序了

            //输出本次排序的结果
            System.out.print("按照第" + digit + "位，本轮排序结果:");
            show(array);

            digit++;//当前所排序的位数+1 下次按照到下一位排序了
        }
    }

    public static void main(String[] args) {
        //int[] a = Template.getIntData(30);
        int[] a = {12, 9, 11, 90, 118, 1, 30, 89, 65, 77, 39, 56};
        System.out.println("基数排序前");

        show(a);
        System.out.println();
        //sort(a, 3);
        System.out.println("基数排序");
        sort(a);

        assert isSorted(a);
        System.out.println("基数排序后");
        show(a);
    }
}
